package 区间;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 57. 插入区间
 * 给你一个 无重叠的 ，按照区间起始端点排序的区间列表 intervals，其中 intervals[i] = [starti, endi] 表示第 i 个区间的开始和结束，并且 intervals 按照 starti 升序排列。同样给定一个区间 newInterval = [start, end] 表示另一个区间的开始和结束。
 * 在 intervals 中插入区间 newInterval，使得 intervals 依然按照 starti 升序排列，且区间之间不重叠（如果有必要的话，可以合并区间）。
 * 返回插入之后的 intervals。
 * 注意 你不需要原地修改 intervals。你可以创建一个新数组然后返回它。
 *
 *
 *  解题步骤：
 *      1、初始化：创建一个结果列表result来存储最终的区间列表
 *      2、遍历区间
 *          将所有在newInterval之前的区间直接添加到result中；
 *          当遇到与newInterval重叠的区间时，合并它们，更新newInterval的起点和结束点；
 *          继续遍历，直到没有重叠的区间；
 *      3、添加合并后的区间：将合并后的newInterval添加到result中。
 *      4、添加剩余区间：将剩余的区间添加到result中。
 *      5 返回结果
 *
 *
 */
public class L_57 {
    public int[][] insert(int[][] intervals, int[] newInterval) {
       List<int[]> result = new ArrayList<>();
       int i = 0;
       int n = intervals.length;
       // 1、添加所有在newInterval之前的区间
        while (i < n && intervals[i][1] < newInterval[0]){
            result.add(intervals[i]);
            i++;
        }
        // 2、合并重叠的区间
        while (i < n && intervals[i][0] <= newInterval[1]){
            newInterval[0] = Math.min(newInterval[0],intervals[i][0]);
            newInterval[1] = Math.max(newInterval[1],intervals[i][1]);
            i++;
        }
        // 添加合并后的区间
        result.add(newInterval);
        // 3:添加剩余的区间
        while (i < n){
            result.add(intervals[i]);
            i++;
        }
        return result.toArray(new int[result.size()][]);
    }
}
